package algorithm.dijkstra;

import java.util.Arrays;

/**
 * 迪杰斯特拉算法 解决图最短路径问题
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-04-07
 */
public class DijkstraAlgorithm {
    static final int N = 65335;

    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = {{N, 5, 7, N, N, N, 2},
                {5, N, N, 9, N, N, 3},
                {7, N, N, N, 8, N, N},
                {N, 9, N, N, N, 4, N},
                {N, N, 8, N, N, 5, 4},
                {N, N, N, 4, 5, N, 6},
                {2, 3, N, N, 4, 6, N}};

        Graph graph = new Graph(vertex, matrix);
        graph.showGraph();

        graph.djs(6);
        graph.show();
    }
}

class Graph {

    private char[] vertex;
    private int[][] matrix;

    private VisitedVertex vv;

    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    public char[] getVertex() {
        return vertex;
    }

    public void setVertex(char[] vertex) {
        this.vertex = vertex;
    }

    public int[][] getMatrix() {
        return matrix;
    }

    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    /**
     * 显示图
     */
    public void showGraph() {
        System.out.println("显示图~~~~");
        for (int[] link : matrix) {
            System.out.println(Arrays.toString(link));
        }
    }


    /**
     * 迪杰特斯拉算法
     *
     * @param index 出发顶点下标
     */
    public void djs(int index) {
        vv = new VisitedVertex(vertex.length, index);
        update(index);
        // 因为上面已经对一个开始结点处理过了 所以这里从1开始
        for (int j = 1; j < vertex.length; j++) {
            index = vv.updateArr();
            update(index);
        }
    }

    /**
     * 更新index下标顶点到周围顶点的距离和前驱顶点
     *
     * @param index 目标顶点下标
     */
    private void update(int index) {
        int len;
        // 只需要针对目标顶底那个一维数组 这里体现广度优先
        for (int j = 0; j < matrix[index].length; j++) {
            // 出发顶点到index顶点的距离 + 从index顶点到j顶点距离
            len = vv.getDis(index) + matrix[index][j];
            if (!vv.in(j) && len < vv.getDis(j)) {
                // 如果发现没有被访问同时此时距离小于之前的距离 就需要更新了
                vv.updatePre(j, index);
                vv.updateDis(j, len);
            }
        }
    }

    /**
     * 显示
     */
    public void show(){
        vv.show();
    }


}

class VisitedVertex {
    // 记录各个顶点是否被访问过 0：未访问 1：已访问
    public int[] already_arr;
    // 每个下标的值为前一个顶点下标
    public int[] pre_vertex;
    // 记录出发顶点到其他顶点的距离
    public int[] dis;

    /**
     * 构造
     *
     * @param length 表示顶点个数
     * @param index  出发顶点下标
     */
    public VisitedVertex(int length, int index) {
        already_arr = new int[length];
        pre_vertex = new int[length];
        dis = new int[length];
        // 标记出发顶点已访问
        already_arr[index] = 1;
        Arrays.fill(dis, 65535);
        dis[index] = 0;
    }

    /**
     * 判断index顶点是否被访问过
     *
     * @param index 下标
     * @return true：访问过；false：未访问
     */
    public boolean in(int index) {
        return already_arr[index] == 1;
    }

    /**
     * 更新出发顶点到index顶点的距离
     *
     * @param index 目标顶点下标
     * @param len   距离
     */
    public void updateDis(int index, int len) {
        dis[index] = len;
    }

    /**
     * 更新index这个顶点的前驱顶点为pre顶点
     *
     * @param index
     * @param pre
     */
    public void updatePre(int index, int pre) {
        pre_vertex[index] = pre;
    }

    /**
     * 返回出发顶点到index顶点的距离
     *
     * @param index 目标顶点index
     * @return 距离
     */
    public int getDis(int index) {
        return dis[index];
    }

    /**
     * 继续选择并返回新的访问顶点
     *
     * @return
     */
    public int updateArr() {
        int min = 65535, index = 0;
        for (int i = 0; i < already_arr.length; i++) {
            // 找到未访问的最小距离下标
            if (already_arr[i] == 0 && dis[i] < min) {
                min = dis[i];
                index = i;
            }
        }
        // 更新已访问
        already_arr[index] = 1;
        return index;
    }

    public void show() {
        System.out.println("开始显示三个数组~~~~");
        for (int i : already_arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
        for (int i : pre_vertex) {
            System.out.print(i + "\t");
        }
        System.out.println();
        for (int i : dis) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}